﻿using System;
using System.Collections.Concurrent;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace DP1
{
    class Program
    {
        static int[,] grid;
        static Dictionary<string, bool> wordsCache = new Dictionary<string, bool>();
        static Dictionary<string, bool> dict = new Dictionary<string, bool>();
        static ConcurrentQueue<string> wordsQueue = new ConcurrentQueue<string>();
        static Graph graph = new Graph();
        static void Main(string[] args)
        {
            dict.Add("CAT", true);
            dict.Add("BAT", true);
            dict.Add("RAT", true);
            dict.Add("ROT", true);
            dict.Add("COT", true);
            dict.Add("DOT", true);
            dict.Add("DOG", true);
            dict.Add("DOM", true);
            dict.Add("CAR", true);
            dict.Add("POT", true);
            //var graph = BuildGraphSimple();
            wordsQueue.Enqueue("CAT");
            BuildGraph("CAT");

            var source = graph.AllNodes.Where(n => n.Name == "CAT").First();
            var dest = graph.AllNodes.Where(n => n.Name == "DOG").First();
            string path = "";
            Console.WriteLine("Shortest Path :" + GetShorestPath(source, dest, out path));
            Console.WriteLine(path);
            //Console.WriteLine("All Shortest Paths :" + AllShorestPaths(source));

            int?[,] adj = graph.CreateAdjMatrix();
            PrintMatrix(ref adj, graph.AllNodes.Count); // We're going to implement that down below
            Console.ReadLine();
        }

        private static Graph BuildGraphSimple()
        {
            var graph = new Graph();
            var a = graph.CreateRoot("A");
            var b = graph.CreateNode("B");
            var c = graph.CreateNode("C");
            var d = graph.CreateNode("D");

            a.AddEdge(b, 7).AddEdge(c, 5).AddEdge(d, 9);
            b.AddEdge(d, 2);
            c.AddEdge(d, 4).AddEdge(b, 1);
            return graph;
        }

        private static void BuildGraph(string word)
        {
            Node currentNode = null;
            if (!wordsCache.ContainsKey(word))
            {
                wordsCache.Add(word, true);
                if ((currentNode = graph.AllNodes.Where(g => g.Name == word).FirstOrDefault()) == null)
                    currentNode = graph.CreateNode(word);
            }
            else
                return;

            List<string> newWords = GetNewWords(word);
            string result;
            wordsQueue.TryDequeue(out result);
            foreach (var item in newWords)
	        {
                if (!wordsCache.ContainsKey(item))
                {
                    if (!wordsQueue.Contains(item))
                        wordsQueue.Enqueue(item);

                    Node child = null;
                    if ((child = graph.AllNodes.Where(g => g.Name == item).FirstOrDefault()) == null)
                        child = graph.CreateNode(item);
                    currentNode.AddEdge(child, 1);
                }
	        }
            foreach (var item in wordsQueue)
            {
                BuildGraph(item);
            }
        }

        private static List<string> GetNewWords(string word)
        {
            List<string> newWords = new List<string>();
            for (int i = 0; i < word.Length; i++)
            {
                for(char ch = 'A'; ch <= 'Z'; ch++)
                {
                    string newWord = word.Replace(word[i], ch);
                    if (dict.ContainsKey(newWord))
                        newWords.Add(newWord);
                }
            }
            return newWords;
        }

        static StringBuilder sb = new StringBuilder();
        private static int GetShorestPath(Node source, Node dest, out string path)
        {
            path = "";
            if (source.Name == dest.Name)
            {
                path = dest.Name;
                return 0;
            }
            int min = 10000, m = 0;
            string minPath = "";
            string finalDest = "";
            foreach (var edge in source.Edges)
            {
                m = edge.Weigth + GetShorestPath(edge.Child, dest, out path);
                if (m <= min)
                {
                    
                    min = m;
                    finalDest = edge.Child.Name;
                    minPath = path;
                    
                    //sb.Append(" " + edge.Parent.Name + "->" +edge.Child.Name +"="+min);                    
                }
                else
                {
                    //sb.Clear();
                    //sb.Append(" " + edge.Parent.Name + "->" + edge.Child.Name + "=" + min);
                }
            }
            //sb.Append(" " + finalDest + "=" + min);
            //Console.WriteLine();
            if (string.IsNullOrEmpty(path))
                path = dest.Name;
            else
                path = source.Name + " " + minPath;
            //if (source.Name == "CAT" && dest.Name == "DOG")
            //    Console.WriteLine(path);
            return min;
        }

        private static void PrintMatrix(ref int?[,] matrix, int Count)
        {
            Console.Write("     ");
            foreach (var item in wordsCache)
            {
                Console.Write("{0} ", item.Key);
            }

            Console.WriteLine();

            var keyList =  wordsCache.Keys.ToArray();
            for (int i = 0; i < wordsCache.Count; i++)
            {
                Console.Write("{0} [ ", keyList[i]);

                for (int j = 0; j < Count; j++)
                {
                    if (i == j)
                    {
                        Console.Write(" 0");
                    }
                    else if (matrix[i, j] == null)
                    {
                        Console.Write(" 0");
                    }
                    else
                    {
                        Console.Write(" {0}", matrix[i, j]);
                    }

                }
                Console.Write(" ]\r\n");
            }
            Console.Write("\r\n");
        }
    }

    public class Node
    {
        public string Name;
        public List<Edge> Edges = new List<Edge>();

        public Node(string name)
        {
            Name = name;
        }

        /// <summary>
        /// Create a new arc, connecting this Node to the Nod passed in the parameter
        /// Also, it creates the inversed node in the passed node
        /// </summary>
        public Node AddEdge(Node child, int w)
        {
            Edges.Add(new Edge
            {
                Parent = this,
                Child = child,
                Weigth = w
            });

            //if (!child.Edges.Exists(a => a.Parent == child && a.Child == this))
            //{
            //    child.AddEdge(this, w);
            //}

            return this;
        }
    }

    public class Edge
    {
        public int Weigth;
        public Node Parent;
        public Node Child;
    }

    public class Graph
    {
        public Node Root;
        public List<Node> AllNodes = new List<Node>();

        public Node CreateRoot(string name)
        {
            Root = CreateNode(name);
            return Root;
        }

        public Node CreateNode(string name)
        {
            var n = new Node(name);
            AllNodes.Add(n);
            return n;
        }

        public int?[,] CreateAdjMatrix()
        {
            int?[,] adj = new int?[AllNodes.Count, AllNodes.Count];

            for (int i = 0; i < AllNodes.Count; i++)
            {
                Node n1 = AllNodes[i];

                for (int j = 0; j < AllNodes.Count; j++)
                {
                    Node n2 = AllNodes[j];

                    var arc = n1.Edges.FirstOrDefault(a => a.Child == n2);

                    if (arc != null)
                    {
                        adj[i, j] = arc.Weigth;
                    }
                }
            }
            return adj;
        }
    }
}
